// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
// 思路，回溯
// 数字和字母要有个映射，根据数字决定遍历深度，每个数字映射的字母列表决定遍历宽度，每个字母列表都是不同的集合，跟之前的组合问题不同，所以不需要startIndex来防止重复
function letterCombinations(digits) {
    let map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz',
    }
    let result = []
    function backtracking(index, s = '') {
        if (index === digits.length) {
            if (s) {
                result.push(s)
            }
            return
        }
        let letters = map[digits[index]]
        if (!letters) {
            return
        }
        for (let i = 0; i < letters.length; i++) {
            backtracking(index + 1, s + letters[i])            
        }
    }
    backtracking(0, '')
    return result
}

console.log(letterCombinations("22"))